In parallel computing, the global reduce operation is widely used for parallel applications. Data are selectively shared among processes in a group to minimize the communications being exchanged among the processes. The Message Passing Interface (MPI) standard defines several collective interfaces for the reduce operation, most notably MPI_REDUCE and MPI_ALLREDUCE. The global reduce operations could be expensive; therefore, efficient MPI_REDUCE and MPI_ALLREDUCE are important. One long-term profiling study demonstrated that the time spent by parallel applications in performing MPI_REDUCE and MPI_ALLREDUCE operations accounted for more than 40% of the time that the applications spent in all MPI functions.
A global reduce operation is collectively performed across all members (i.e., all processes) of a process group defined by the MPI communicator. For purposes of the instant invention, commutative reduce operations, which are most widely used, will be detailed. In a communicator group, each process has an equal length input vector of data. The global reduce operation combines all input vectors using the specified operation. Processes exchange data and perform local reduce operations to yield partial reduce results. Partial reduce results are exchanged and combined until complete reduce results are generated. In MPI_REDUCE, the full vector with the complete reduce result for the reduce operation returns at one process, known as the root. In MPI_ALLREDUCE, complete reduce results return at every process of the communicator group.
For a small message MPI_REDUCE the best known algorithm is the Minimum Spanning Tree (MST) algorithm in which the root of the MPI_REDUCE is the root of a process MST. A process on the tree first receives messages containing vectors from all of its children and then combines the received data with its own input vector. The process then sends the result vector to its parent process. In MPI_ALLREDUCE, one process is selected as the root. Once the root receives and combines vectors and gets the final result, it broadcasts the result to other member of the communicator group. The cost of the MST MPI_REDUCE algorithm can be modeled by the following if the MST is a binomial tree:T=log(N)*(α+L*β+L*γ),where;
α is the latency of each message
β is the communication cost per byte
γ is the local reduce cost per byte
N is the number of process is the communicator; and
L is the length of a process's input vector to the reduce operation.
Clearly for large messages, the MST algorithm is not efficient since every processor would have to perform the reduce operation on full vectors all the time, rather then taking advantage of the parallelism. Better algorithms have been developed for large message MPI_REDUCE and MPI_ALLREDUCE operations. One such algorithm is the Recursive Halving Recursive Doubling (RHRD) algorithm. In the RHRD algorithm for MPI_REDUCE, each process takes log(N) steps of computation and communication. The computation stage of the steps is preceded by a distribution stage during which the processes exchange data (i.e., vector information) with other processes. In the first step of the distribution stage, also referred to as the preparation stage, process i exchanges with process j half of their input vectors where j=(i ^ mask). Symbol ^ denotes a bitwise exclusive “OR” operation, and “mask” equals 1's binary representation. If i<j, process j sends the first half of its vector to process i and receives the second half of process i's vector. Process i combines the first half of the two vectors and process j combines the second half of the two vectors.
In the second step, process i and process j exchange half of their intermediate reduce results from the first step and combine the received data with the half that was not sent, where j=i ^ mask and mask is 1's binary representation left-shifting 1 bit. At step k, process i and process j exchange half of their intermediate reduce results from step (k−1), and combine the received part with the half that was not sent, where j=i ^ mask and mask is 1's binary representation left shifting (k−1) bits, if i<j, process i sends the second half of the intermediate result and receives the first half.
This procedure continues recursively, halving the size of exchanged and combined data at each step, for a total of log(N) steps. Each process owns 1/N of the result vector in the end: process 0 owns the first 1/N, process 1 owns the second 1/N, process i owns the (i−1)th 1/N and so on. In MPI_REDUCE, the root then performs a gather operation to gather the rest of the complete reduce results back from other processes. The vectors are exchanged between processes by passing messages. Clearly the larger the vector, the larger the message and the higher the overhead and the greater the potential latency for message exchange.
In MPI_ALLREDUCE, an allgather step is performed instead of a gather step, in which every process gathers the complete reduce results from other processes. The cost of the RHRD algorithm can be modeled by:T=2*log(N)*α+2*(N−1)/N*L*β+(N−1)/N*L*γ. 
When the message size is large based on the larger vector length, the RHRD algorithm performs better than the MST algorithm, since the latency term “α” is small compared to the size of the other two terms in the algorithm and can essentially be ignored.
The RHRD algorithm applies only to “power of two” processes. Studies have shown that a reduce operation is widely performed on non-power of two processes as well. For non-power of two N′ processes, the prior art solution performs one extra preparation step at the beginning of the operation than the RHRD algorithm. In addition, for the MPI_ALLREDUCE case, another extra step is performed at the end of the operation. The beginning step is to exclude r processes from the algorithm, where r=N′−N, with N being the largest power of two less than N′. The first 2*r processes exchange input vectors. Of the first 2*r processes, those with even ranks send the second half of their vectors to their right neighbors and those with odd ranks send the first half of their vectors to their left neighbors. Once the exchange of vector information is completed, the first 2*r processes perform a local reduce operation. Those with odd ranks then send their local reduce results to their left neighbors and do not participate in the rest the algorithm. Other processes, N of them, follow the algorithm described previously for power of two processes. In MPI_ALLREDUCE, those processes excluded by the first step receive final results from their left neighbors in the final step.
FIG. 1 shows the prior art process flow for an MPI_ALLREDUCE operation on seven (i.e., a non-power of two) processes, assuming a large vector of size 4, containing elements ABCD. Partial reduce operation results are represented by element and rank number (in subscript), e.g., A-B0-3 represents reduce results of element A-B of processes 0, 1, 2, and 3.
The cost of the prior art approach on non-power of two processes can be modeled by:T=(2+2*log(N))*α+(1+2*(N−1)/N)*L*β+(½+(N−1)/N)*L*γ.  (1)for MPI_REDUCE andT=(3+2*log(N))*α+(2+2*(N−1)/N)*L*β+(½+(N−1)/N)*L*γ.  (2)for MPI_ALLREDUCE.
The extra step or steps for non-power of two processes increase bandwidth requirements by more than 50% for MPI_REDUCE and 100% for MPI_ALLREDUCE. Clearly, therefore, it is desirable, and an object of the present invention, to provide an improved method of performing large message MPI_REDUCE/MPI_ALLREDUCE operations for non-power of two processes.
It is another object of the present invention to improve performance of large message MPI_REDUCE and MPI_ALLREDUCE operations by removing unnecessary data forwarding in the preparation step of the prior art algorithm.
Yet another object is to fully utilize interconnect bandwidth in the final step for MPI_ALLREDUCE by rearranging the flow of partial reduce results.